GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Behälterproblem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Behälterproblem</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Das <b>Behälterproblem</b> oder auch <b>bin packing problem</b> ist ein <a href="Kombinatorische_Optimierung" title="Kombinatorische Optimierung">kombinatorisches Optimierungsproblem</a>, das auf folgender Fragestellung basiert:

</p>

<ul><li><i>Gegeben:</i> Eine Anzahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\in \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2a5bc4b7383031ba693b7433198ead7170954c1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.73ex; height:2.176ex;" alt="{\displaystyle k\in \mathbb {N} }" loading="lazy"></span> von „Behältern“ (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> <i>bin</i>) der Größe <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\in \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/07b2dd48f69fc66310b6f437f9f0de49bfb7d787.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.516ex; height:2.176ex;" alt="{\displaystyle b\in \mathbb {N} }" loading="lazy"></span> und eine Anzahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d059936e77a2d707e9ee0a1d9575a1d693ce5d0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.913ex; height:2.176ex;" alt="{\displaystyle n\in \mathbb {N} }" loading="lazy"></span> „Objekte“ mit den Größen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1},a_{2},\dotsc ,a_{n}\ \leq \ b}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1},a_{2},\dotsc ,a_{n}\ \leq \ b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/554fd373a46c8e96ad559d161d4e7a7e579be1dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.486ex; height:2.509ex;" alt="{\displaystyle a_{1},a_{2},\dotsc ,a_{n}\ \leq \ b}" loading="lazy"></span>.</li>

<li><i>Frage:</i> Können die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> „Objekte“ so auf die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> „Behälter“ verteilt (<i>packing</i>) werden, dass keiner der „Behälter“ überläuft? Formal:</li></ul>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \exists \ f\colon \{1,\dotsc ,n\}\to \{1,\dotsc ,k\}{\text{, so dass für alle }}j\in \{1,\dotsc ,k\}\quad \sum _{f(i)=j}a_{i}\leq b{\text{ gilt?}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9eb086194fbc8bc3e0caeb47a5e742d3c941c53b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:76.825ex; height:6.009ex;" alt="{\displaystyle \exists \ f\colon \{1,\dotsc ,n\}\to \{1,\dotsc ,k\}{\text{, so dass für alle }}j\in \{1,\dotsc ,k\}\quad \sum _{f(i)=j}a_{i}\leq b{\text{ gilt?}}}" loading="lazy"></span></dd></dl></dd></dl>

<p>Das oben beschriebene <a href="Entscheidungsproblem" class="mw-redirect" title="Entscheidungsproblem">Entscheidungsproblem</a> ist <a href="NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">NP-vollständig</a>; das zugehörige <a href="Optimierungsproblem" title="Optimierungsproblem">Optimierungsproblem</a> – das Finden einer Zuordnung, bei der die Anzahl an Behältern minimiert wird – ist <a href="NP-Schwere" title="NP-Schwere">NP-schwer</a>.

</p><p>Die hier gegebene Formulierung des Bin-Packing-Problems ist nur die Motivation beziehungsweise Basis für eine Vielzahl weiterer <i>Packing-Problems</i>, die unter anderem in der <a href="Verpackung" title="Verpackung">Verpackungsindustrie</a> eine große Rolle spielen.

</p><p>Eine etwas allgemeiner formale Definition beschreibt das Bin-Packing-Problem als die Bestimmung einer <a href="Partition_(Mengenlehre)" title="Partition (Mengenlehre)">Partition</a> und Zuordnung einer <a href="Menge_(Mathematik)" title="Menge (Mathematik)">Menge</a> von Objekten, so dass eine bestimmte Bedingung erfüllt bzw. eine Zielfunktion minimiert oder maximiert wird.

</p><p>Man unterscheidet zwischen Offline- und Online-Varianten, wobei offline bedeutet, dass im Voraus alle Objekte bekannt sind. Bei Online-Verfahren muss sofort entschieden werden, in welchen Behälter das Objekt gepackt wird, ohne die folgenden Objekte zu kennen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithmen">Algorithmen</h2></div>

<p>Da Bin-Packing ein NP-schweres Problem ist, ist es <a href="P-NP-Problem" title="P-NP-Problem">vermutlich</a> unmöglich, es in polynomialer Laufzeit zu lösen. Johnsons <a href="Approximationsalgorithmus" title="Approximationsalgorithmus">Approximationsalgorithmus</a> <i>First Fit Decreasing</i> löst das Problem in polynomieller Zeit mit einer asymptotischen <a href="G%C3%BCtegarantie" class="mw-redirect" title="Gütegarantie">Gütegarantie</a> von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 11 \over 9}">

<mfrac>

</mstyle>

</mfrac>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 11 \over 9}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5144e48398e454d94847da1d98cb59c5647804cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:3.161ex; height:5.176ex;" alt="{\displaystyle 11 \over 9}" loading="lazy"></span>.

</p>

<ol><li>Sortiere die Objekte nach absteigender Größe</li>

<li>Füge die Objekte der Reihe nach ein, sodass jedes in den ersten Behälter gegeben wird, in dem noch genug Platz ist.</li>

<li>Falls in keinem der bereits geöffneten Behälter genügend Platz ist, öffne einen neuen.</li></ol>

<p>Die Laufzeit beträgt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\cdot \log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot \log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9aaa0e99aa50f586bff0578a16e55dffcd9d5bf7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.487ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot \log n)}" loading="lazy"></span> (sowohl für das Sortieren, als auch für das Einfügen).

Dieselben Resultate gelten auch für <i>Best Fit Decreasing</i>. Dabei wird ein Objekt nicht in den ersten Behälter eingefügt, in den es passt, sondern in den Behälter, in den es gerade noch passt (die Restkapazität wird also minimiert).

</p><p>Bei der Online-Variante ist es nicht möglich, die Objekte im Voraus nach Größe zu sortieren. Die Algorithmen <i>First Fit</i> und <i>Best Fit</i> arbeiten analog zu den oben genannten, jedoch ohne vorheriges Sortieren. Beide <a href="Algorithmus" title="Algorithmus">Algorithmen</a> haben eine scharfe asymptotische Gütegarantie von 1,7 und eine Laufzeit von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\cdot \log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot \log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9aaa0e99aa50f586bff0578a16e55dffcd9d5bf7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.487ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot \log n)}" loading="lazy"></span>. <i>Best Fit</i> sucht in allen bisher vorhandenen Behältern nach dem kleinsten noch passenden freien Platz.

</p><p>Der naive Algorithmus <i>Next Fit</i> packt die Objekte der Reihe nach in den letzten geöffneten Behälter, falls sie hineinpassen. Ansonsten wird der Behälter geschlossen, ein neuer geöffnet und das aktuelle Objekt in den leeren Behälter gegeben. Die asymptotische Gütegarantie beträgt 2, die Laufzeit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"></span>. Der Vorteil dieses naiven Algorithmus ist, dass immer nur ein Behälter gleichzeitig geöffnet ist (was in der praktischen Anwendung eine Bedingung sein kann).

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Bernhard Korte, Jens Vygen: <i>Kombinatorische Optimierung.</i> Springer, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7, S. 485ff</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://pdfs.semanticscholar.org/bb99/86af2f26f7726fcef1bc684eac8239c9b853.pdf?_ga=1.50320358.1394974689.1485463187">Optimizing Three-Dimensional Bin Packing</a></li>

<li><a rel="nofollow" class="external text" href="https://algo.rwth-aachen.de/~algorithmus/algo24.php">Artikel im <i>Algorithmus der Woche</i></a></li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-06-05" href="https://de.wikipedia.org/wiki/?title=Beh%C3%A4lterproblem&oldid=256712411">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>